package wikisearch.cluster;

import org.jgrapht.alg.*;
import org.jgrapht.graph.DefaultWeightedEdge;

import wikisearch.datastructures.*;
import java.util.*;
import org.jgraph.graph.*;

/**
 * A very simple clustering criteria, where all it does is take minimum edges out.
 * 
 * @author hcho33
 *
 */
public class SimpleCluster {

	private KruskalMinimumSpanningTree<?, WEdge> mst = null;
	private LinkedList<WEdge> ll = null;
	private Graph g = null;
	private HashSet<WEdge> removedEdges = null;
	
	/**
	 * Assumes we want to remove low weights
	 * @param g
	 * @param numClusters
	 */
	public SimpleCluster(Graph g, int numClusters) {
		
		this.g = g;
		mst = new KruskalMinimumSpanningTree(g);
		ll = new LinkedList<WEdge>(mst.getEdgeSet());
		removedEdges = new HashSet<WEdge>();
		sortEdges();
		cluster(numClusters);
	}
	
	@SuppressWarnings("unchecked")
	private void sortEdges() {

		Collections.sort(ll, g.getComparator());
	}
	
	private void cluster(int takeout) {
		
		for (int i = 0; i < takeout; i++)
			removedEdges.add(ll.get(i));
		int cid = 0;
		
		HashSet<WEdge> seen = new HashSet<WEdge>();
		for (WEdge e : removedEdges) {
			
			String s = g.getEdgeSource(e);
			String t = g.getEdgeTarget(e);
			Set<WEdge> adjacentEdges = g.edgesOf(s);
			traverseAndLabelCID(adjacentEdges, seen, cid);
			cid++;
			adjacentEdges = g.edgesOf(t);
			traverseAndLabelCID(adjacentEdges, seen, cid);
			cid++;
		}
	} //take out is number of edges to take out.
	
	private void traverseAndLabelCID(Set<WEdge> edges, HashSet<WEdge> seen, int cid) {
		
		Set<WEdge> es = mst.getEdgeSet();
		for (WEdge e : edges) {
			
			if (!removedEdges.contains(e) && !seen.contains(e) && es.contains(e)) {
				
				seen.add(e);
				e.cid = cid;
				String s = g.getEdgeSource(e);
				String t = g.getEdgeTarget(e);
				HashSet<WEdge> adjs = new HashSet<WEdge>(g.edgesOf(s));
				adjs.addAll(g.edgesOf(t));
				traverseAndLabelCID(adjs, seen, cid);
			}
		}
	}
	
	public void print() {
		
		for (WEdge e : g.edgeSet()) { //mst.getEdgeSet()) {
			
			System.out.println("" + e.toString() + " - weight : " + g.getEdgeWeight(e) + " cid : " + e.cid);
		}
		
	}
}
